package com.dmall.directed.graph;

import java.io.File;
import java.util.Scanner;
import java.util.TreeSet;

/**
 * 无权图
 * 既支持有向，也支持无向
 * @author: xiao1.wang
 * @date: 2022-09-03 23:11:16
 */
public class Graph implements Cloneable {
    private int V;
    private int E;
    private TreeSet<Integer>[] adj;
    private boolean directed;
    private int[] indegrees;
    private int[] outdegrees;

    private Graph() {}

    public Graph(String filePath, boolean directed) {

        this.directed = directed;

        File file = new File(filePath);
        try (Scanner scanner = new Scanner(file)) {
            V = scanner.nextInt();
            if (V < 0) {
                throw new IllegalArgumentException("V must be non-negative");
            }
            adj = new TreeSet[V];
            for (int i = 0; i < V; i++) {
                adj[i] = new TreeSet<>();
            }

            indegrees = new int[V];
            outdegrees = new int[V];

            E = scanner.nextInt();
            if (E < 0) {
                throw new IllegalArgumentException("E must be non-negative");
            }
            for (int i = 0; i < E; i++) {
                int a = scanner.nextInt();
                validateVertex(a);
                int b = scanner.nextInt();
                validateVertex(b);
                if (a == b) {
                    throw new IllegalArgumentException("Self Loop is Detected!");
                }
                if (adj[a].contains(b)) {
                    throw new IllegalArgumentException("Parallel Edges are Detected!");
                }
                adj[a].add(b);
                if (directed) {
                    outdegrees[a] ++;
                    indegrees[b] ++;
                }

                if (!directed) {
                    adj[b].add(a);
                }
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    public Graph(String filePath) {
        this(filePath, false);
    }

    public Graph reverseGraph() {
        Graph g = new Graph();
        g.V = this.V;
        g.E = this.E;
        g.adj = new TreeSet[this.V];
        for (int v = 0; v < this.V; v++) {
            g.adj[v] = new TreeSet<>();
        }
        g.directed = this.directed;
        g.indegrees = new int[this.V];
        g.outdegrees = new int[this.V];
        for (int v = 0; v < this.V; v++) {
            for (int w : this.adj(v)) {
                g.adj[w].add(v);
                g.outdegrees[w] ++;
                g.indegrees[v] ++;
            }
        }
        return g;
    }

    public boolean isDirected() {
        return directed;
    }

    public void validateVertex(int v) {
        if (v < 0 || v >= V) {
            throw new IllegalArgumentException("vertex " + v + "is invalid");
        }
    }

    public int V() {
        return V;
    }

    public int E() {
        return E;
    }

    public boolean hasEdge(int v, int w) {
        validateVertex(v);
        validateVertex(w);
        return adj[v].contains(w);
    }

    public Iterable<Integer> adj(int v) {
        validateVertex(v);
        return adj[v];
    }

    public int degree(int v) {
        if (directed) {
            throw new RuntimeException("degree only works in undirected graph.");
        }
        validateVertex(v);
        return adj[v].size();
    }

    public int indegree(int v) {
        if (!directed) {
            throw new RuntimeException("indegree only works in directed graph.");
        }
        validateVertex(v);
        return indegrees[v];
    }

    public int outdegree(int v) {
        if (!directed) {
            throw new RuntimeException("outdegree only works in directed graph.");
        }
        validateVertex(v);
        return outdegrees[v];
    }

    public void removeEdge(int v, int w) {
        validateVertex(v);
        validateVertex(w);

        if (adj[v].contains(w)) {
            E --;
            if (directed) {
                outdegrees[v] --;
                indegrees[w] --;
            }
        }

        adj[v].remove(w);
        if (!directed) {
            // 无向图才会都删除
            adj[w].remove(v);
        }
    }

    public void addEdge(int v, int w) {
        validateVertex(v);
        validateVertex(w);
        adj[v].add(w);
        if (!directed) {
            adj[w].add(v);
        }
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(String.format("V = %d, E = %d, directed=%b\n", V, E, directed));
        for (int v = 0; v < V; v++) {
            sb.append(String.format("%d: ", v));
            for (int w : adj[v]) {
                sb.append(String.format("%d ", w));
            }
            sb.append('\n');
        }
        return sb.toString();
    }

    @Override
    public Object clone() {
        try {
            Graph cloned = (Graph) super.clone();
            cloned.adj = new TreeSet[V];
            for (int v = 0; v < V; v++) {
                cloned.adj[v] = new TreeSet<>();
                for (int w : adj[v]) {
                    cloned.adj[v].add(w);
                }
            }
            return cloned;
        } catch (CloneNotSupportedException e) {
            return null;
        }
    }

    public static void main(String[] args) {
        String filePath = Graph.class.getClassLoader().getResource("com/dmall/directed/graph/ug.txt").getPath();
        Graph graph = new Graph(filePath, true);
        System.out.println(graph);

        for (int v = 0; v < graph.V(); v++) {
            System.out.println(graph.indegree(v) + ":" + graph.outdegree(v));
        }
    }
}
